package _18_剑指OfferII;

import java.util.*;

public class _109_剑指OfferII开密码锁 {

    public static void main(String[] args) {
        String[] str = {"1301","0113","0202","0122","3012","0131","0200","0203","1232","0222"};
        String target = "2311";
        _109_剑指OfferII开密码锁 v = new _109_剑指OfferII开密码锁();

        System.out.println(v.openLock(str, target));
    }

    // 最短路径，或者最短什么一般都是使用广度优先搜索完成
    // 使用双向bfs，只是用单项的话，会出现空间爆炸，递归超时的情况
    // 如果是一个目的地到某个目的地，并且求最小到达距离，可以使用双向dfs解决
    public int openLock(String[] deadends, String target) {
        Set<String> originSet = new HashSet<>(Arrays.asList(deadends));
        String start = "0000";
        if (start.equals(target)) return 0;
        if (originSet.contains(start) || originSet.contains(target)) return -1;
        // 双向bfs求解
        Queue<String> startQueue = new LinkedList<>(), endQueue = new LinkedList<>();
        startQueue.add(start);
        endQueue.add(target);
        Map<String, Integer> startMap = new HashMap<>(), endMap = new HashMap<>();
        startMap.put(start, 0);
        endMap.put(target, 0);

        while (!startQueue.isEmpty() && !endQueue.isEmpty()) {
            if (startQueue.size() > endQueue.size()) {
                Queue<String> qt = startQueue;
                startQueue = endQueue;
                endQueue = qt;
                Map<String, Integer> mt = startMap;
                startMap = endMap;
                endMap = mt;
            }

            int size = startQueue.size();
            while (size-- > 0) {
                String cur = startQueue.poll();
                char[] curChars = cur.toCharArray();
                int step = startMap.get(cur);
                for (int i = 0; i < 4; ++i) {
                    char oldChar = curChars[i];
                    for (int j = -1; j <= 1; j += 2) {
                        int newNum, n;
                        // 枚举
                        newNum = (n = curChars[i] - '0' + j) == -1 ? 9 : n % 10;
                        curChars[i] = (char)(newNum + '0');
                        String newStr = String.valueOf(curChars);
                        // 恢复原始值
                        curChars[i] = oldChar;
                        if (originSet.contains(newStr) || startMap.containsKey(newStr)) continue;
                        if (endMap.containsKey(newStr)) {
                            return step + 1 + endMap.get(newStr);
                        }
                        // 存放队列
                        startQueue.add(newStr);
                        startMap.put(newStr, step + 1);
                    }
                }
            }
        }
        return -1;
    }

}
